import util.TreeNode;

import java.util.*;

/**
 * Created by loso on 2017/3/10.
 */
public class _107_BinaryTreeLevelOrderTraversalII {
    public static void main(String[] args) {

    }

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        putMap(1,root);
        List<List<Integer>> list1 = new ArrayList<>();
        for (List l :
                list) {
            list1.add(0,l);
        }
        return list1;
    }

    public void putMap(int level, TreeNode root){
        if (root == null){
            return;
        }
        if (list.size()<level){
            list.add(new ArrayList<>());
        }
        list.get(level-1).add(root.val);
        putMap(level+1,root.left);
        putMap(level+1,root.right);
    }


    //重要
    //通过直接进行size和level的相减直接就倒序的添加list
    private void addLevel(LinkedList<List<Integer>> list, int level, TreeNode node) {
        if (node == null) return;
        if (list.size()-1 < level) list.addFirst(new LinkedList<Integer>());
        list.get(list.size()-1-level).add(node.val);
        addLevel(list, level+1, node.left);
        addLevel(list, level+1, node.right);
    }
}
